/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-11-25
 * Time: 0:01
 */
public class Solution1 {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        //删除标记位
        boolean flag = false;
        //记录回溯
        int backLeft = -1;
        int backRight = -1;

        while (left < right) {
            char start = s.charAt(left);
            char end = s.charAt(right);
            if (start == end) {
                left++;
                right--;
            }else {
                if (flag && backLeft == -1) {
                    //如果start和end不同，且删除次数已使用
                    return false;
                }
                if (backLeft == -1) {
                    //记录当前不同的位置
                    backLeft = left;
                    backRight = right;
                    //尝试删除左边
                    left++;
                    flag = true;
                }else {
                    //删出左边走不通，尝试走右边
                    left = backLeft;
                    right = backRight;
                    right--;
                    backLeft = -1;
                }
            }
        }

        return true;
    }
}
